#ifndef MATRIXGRAPH_H_
#define MATRIXGRAPH_H_

#include <boost/pool/object_pool.hpp>
#include <boost/optional.hpp>

#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/impls/BaseGraphTmpl.h"
#include "graph_support/impls/Edge.h"
#include "graph_support/impls/matrix/MatrixEdgeIterator.h"

namespace GRAPH_SUPPORT_NS
{
namespace impls
{
namespace matrix
{

template <
			typename VertexT = int,
			typename EdgeAttributesT = attributes::Length1EdgeAttributes,
			typename HashFn = stdext::hash< VertexT >,
			typename CmpFn = stdext::equal_to< VertexT >,
			typename VertNumResolver = utils::ResolveTableHash< VertexT, size_t, HashFn, CmpFn >
			>
class MatrixGraphTmpl : public BaseGraphTmpl< VertexT, HashFn, CmpFn, VertNumResolver >
{
private:
	typedef BaseGraphTmpl< VertexT, HashFn, CmpFn, VertNumResolver > Super;
	typedef MatrixGraphTmpl< VertexT, EdgeAttributesT, HashFn, CmpFn, VertNumResolver > MyT;
public:
	typedef VertexT GrVertex;
	typedef EdgeAttributesT EdgeAttributes;
	typedef Edge< GrVertex, GrVertex, EdgeAttributes > GrEdge;
	typedef GrEdge * GrEdgePtr;
	typedef typename Super::VertexIterator VertexIterator;
	typedef MatrixEdgeIterator< GrEdge > EdgeIterator;
private:
	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributes >::IAttributes IEdgeAttributes;
//	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributes >::Attributes IEdgeAttributesImpl;

public:
	template< typename IterT >
	MatrixGraphTmpl( IterT verticesBeg, IterT verticesEnd, bool isBidirected = false )
		: Super( verticesBeg, verticesEnd, isBidirected )
	{
		init( verticesBeg, verticesEnd );
	}

	template< typename CollT >
	MatrixGraphTmpl( const CollT & vertsColl, bool isBidirected = false )
		: Super( vertsColl.begin(), vertsColl.end(), isBidirected )
	{
		init( vertsColl.begin(), vertsColl.end() );
	}

	EdgeIterator getEdgsBeg( const GrVertex & v )
	{
		size_t vid = vert2num( v );
		return getEdgsBegId( vid );
	}

	EdgeIterator getEdgsEnd( const GrVertex & v )
	{
		size_t vid = vert2num( v );
		return getEdgsEndId( vid );
	}

// TODO 7 [blocked - performance] simplify iterator and view to performance test
	EdgeIterator getEdgsBegId( size_t vid )
	{
		Super::checkVIDValid( vid );
		size_t n = Super::getVertexCount();
		return EdgeIterator( matrix[vid], matrix[vid], matrix[vid] + n );
	}

	EdgeIterator getEdgsEndId( size_t vid )
	{
		Super::checkVIDValid( vid );
		size_t n = Super::getVertexCount();
		return EdgeIterator( matrix[vid], matrix[vid] + n, matrix[vid] + n );
	}

	template< typename FnT >
	void forEachOutEdge( GrVertex v, const FnT & fn )
	{
		forEachOutEdgeId( Super::vert2num( v ), fn );
	}

	template< typename FnT >
	void forEachOutEdgeId( size_t vid, const FnT & fn )
	{
		// TODO: proper implementation
		Super::checkVIDValid( vid );
		std::for_each( getEdgsBegId( vid ), getEdgsEndId( vid ),
				boost::bind( fn, boost::bind( & utils::ptr2ref< GrEdge, GrEdgePtr >, _1 ) ) );
	}

	virtual IGraph::IEdgeIteratorPtr igetOutEdgesIterator( size_t vid )
	{
		return IGraph::IEdgeIteratorPtr( new WrapEdgeIterator< EdgeIterator, MyT >( * this, getEdgsBegId( vid ), getEdgsEndId( vid ) ) );
	}

	virtual void igetOutEdgesIterator( size_t vid, IGraph::IEdgeIterator & iter )
	{
		WrapEdgeIterator< EdgeIterator, MyT > * iterptr = dynamic_cast< WrapEdgeIterator< EdgeIterator, MyT > * >( & iter );
		if ( iterptr == NULL )
		{
			throw GRAPH_SUPPORT_NS::exceptions::BadGraphItemException();
		}
		* iterptr = WrapEdgeIterator< EdgeIterator, MyT >( * this, getEdgsBegId( vid ), getEdgsEndId( vid ) );
	}

	boost::optional< GrEdgePtr > findEdge( const GrVertex & beg, const GrVertex & end )
	{
		size_t begId = vert2num( beg );
		Super::checkVIDValid(begId);
		size_t endId = vert2num( end );
		Super::checkVIDValid(endId);
		GrEdgePtr result = matrix[begId][endId];
		return result == NULL ?
				boost::optional< GrEdgePtr >() :
				boost::optional< GrEdgePtr >( result );
	}

// modify
public:
	void addEdge( const GrVertex & beg, const GrVertex & end, const EdgeAttributes & edgeAttrs = EdgeAttributes() )
	{
		size_t begVid = vert2num( beg );
		Super::checkVIDValid(begVid);
		size_t endVid = vert2num( end );
		Super::checkVIDValid(endVid);

		GrEdgePtr edge = addSingleEdge( begVid, endVid, edgeAttrs );
		if ( Super::isBidirected )
		{
			GrEdgePtr redge = addSingleEdge( endVid, begVid, edgeAttrs );

			edge->getAttributes().onBidirEdgeCreated( redge->getAttributes(), true );
			redge->getAttributes().onBidirEdgeCreated( edge->getAttributes(), false );
		}
	}

	virtual void iaddEdge( size_t begVid, size_t endVid, const IGraph::IEdgeAttributesPtr & iattrs )
	{
		IEdgeAttributes * attrs = dynamic_cast< IEdgeAttributes * >( iattrs.get() );
		assert( attrs != NULL );
		GrVertex beg = Super::num2vert( begVid );
		GrVertex end = Super::num2vert( endVid );
		addEdge( beg, end, * attrs->get() );
	}

private:
	GrEdgePtr addSingleEdge( size_t begVid, size_t endVid, const EdgeAttributes & edgeAttrs )
	{
		// TODO: this is unsafe
		matrix[begVid][endVid] = new ( edgesPool.malloc() )
				GrEdge( begVid, endVid, Super::vertices, edgeAttrs );
		return matrix[begVid][endVid];
	}

	template< typename IterT >
	void init( IterT beg, IterT end )
	{
		std::copy( beg, end, Super::vertices.begin() );

		size_t vertexCount = Super::getVertexCount();
		matrixBuf.resize( vertexCount * vertexCount, NULL );
		matrixLinksBuf.resize( vertexCount, NULL );
		for ( int i = 0; i < vertexCount; i++ )
		{
			matrixLinksBuf[i] = &matrixBuf[i * vertexCount];
		}
		matrix = &matrixLinksBuf[0];
	}

private:
	GrEdgePtr * * matrix;
	std::vector< GrEdgePtr > matrixBuf;
	std::vector< GrEdgePtr * > matrixLinksBuf;
	boost::object_pool< GrEdge > edgesPool;
};

}
}
}

#endif /* MATRIXGRAPH_H_ */
